/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* nextGreaterElement(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {

    // step 1# 初始化栈
    int top = -1;  // 栈顶指针（初始空栈）
    int stack_len = nums2Size;
    int stack[stack_len];  // 栈数组，最多存nums2Size个元素

    // step 2# 初始化 nums2 每个元素对应的下一个更大元素结果数组
    int* result_nums2 = (int *)malloc(sizeof(int) * nums2Size);

    // step 3# 初始化最终返回的结果数组
    int* result = (int *)malloc(sizeof(int) * nums1Size);
    *returnSize = nums1Size;  // 设置返回数组大小

    // step 4# 栈中先放入第一个元素下标（准备单调栈处理）
    stack[++top] = 0;  // 注意这里放的是下标

    // step 5# 初始化 result_nums2，默认都为-1（代表找不到更大的数）
    for (int i = 0; i < nums2Size; i++) {
        result_nums2[i] = -1;
    }

    // step 6# 单调栈处理 nums2，找每个元素的下一个更大元素
    for (int i = 1; i < nums2Size; i++) {
        if (nums2[i] <= nums2[stack[top]]) {
            // step 6.1# 当前元素 <= 栈顶元素，入栈
            stack[++top] = i;
        } else {
            // step 6.2# 当前元素 > 栈顶元素，不断弹栈并记录
            while ((top >= 0) && (nums2[i] > nums2[stack[top]])) {
                result_nums2[stack[top]] = nums2[i];  // 更新栈顶元素的结果
                top--;  // 弹栈
            }
            // step 6.3# 当前元素入栈
            stack[++top] = i;
        }
    }

    // step 7# 根据nums1中的元素，在result_nums2里查找对应结果
    for (int i = 0; i < nums1Size; i++) {
        for (int j = 0; j < nums2Size; j++) {
            if (nums1[i] == nums2[j]) {
                result[i] = result_nums2[j];
            }
        }
    }

    // step 8# 返回最终结果数组
    return result;
}
